package sum_of_two_numbers

import(
)

//SumOfTwoNumbers 两数之和等于目标数字
//算法时间复杂度最坏：O(n)
//空间复杂度：O(n)
func SumOfTwoNumbers(nums []int, target int) []int {
	m := getNumMaps(nums)
	for v, p := range m {
		if len(m[v]) > 1  {
			m[v] = m[v][1:]
		} else {
			delete(m, v)
		}
		d := target - v
		if sl, ok := m[d]; ok{
			return []int{p[0], sl[0]}
		}
	} 
	return nil
}

func getNumMaps(nums []int) map[int][]int {
	m := make(map[int][]int)
	for k, v := range nums {
		m[v] = append(m[v], k)
	}
	return m
} 